This invention relates to a mechanism for packing plural segments into a page freme within a computer main store. The computer store includes main store and devices external to main store which may be called input/output or source/sink devices. Computer store is divided into a large number of equal parts called page frames (e.g. 2,048 or 4,096 bytes in size).
A segment is an entity conprising a contiguous range of addressability which is used by the hardware of a computer system for locating data in the store of the system.
Segments may be created in varying sizes, while page frames are fixed in size. Either may have its size measured in bytes. Segments which cannot change their size after their creation are called "fixed" segments, but "varying" segments can have their size changed after their creation. Segment size can vary from a small fraction of a page frame to a very large number of page frames, for example from 0 to 2.sup.24 bytes.
A small segment may be defined as a segment which is less than a predetermined part of a page frame in size, and a large segment is defined as greater than the predetermined part of a page frame in size.
Fundamentally the wide range of segment sized is incompatible with the fixed page size. Yet segments, or parts of segments, must be put into page frames before the segments can be used by executing programs. A potentially high wastage of main store use can result from this incompatability, since a segment may be so small as to occupy only a small part of a page frame, with the result that most of the space in the page frame is unused.
If the segment is large it may occupy a large number of page frames in which case the segment may be divided into a number of pages each being transferrable into a page frame hardware unit in the main store. Large segments are therefore relatively compatible with page frames because only the last page of a segment may leave unused space in a segment; hence large segments result in low waste.
This invention is directed primarily at reducing the size incompatibility between page frames and small segments, although it consistently handles all sizes of segments whether they are small or large, fixed or variable. The invention does this by supporting the packing of plural segments into a singel page frame. Page frame packing includes putting only plural fixed small segments into a page frame, or putting into a page frame plural fixed small segments with a whole or part of a varying segment or a part of a large segment.
The invention can greatly improve the efficiency in the system use of main store by providing a broad solution to the basic incompatibility between fixed small segments and the main store's page frame size.
The invention also supports the accessing of data in a segment which may begin at any of plural partitions provided in a page frame. The invention is interfaced with a segmented virtual addressing system in a way that provides access to any byte in any segment in a consistent manner whether or not the access is to packed or unpacked page frames.
Segmented addressing conventionally uses the address format shown in FIG. 6A to locate any byte in any segment, although the addressing format in FIG. 6A excludes the use of this invention. FIG. 6A shows a segment address which contains a SID (Segment Identifier) field which identifies the segment, a page field for locating a page in the segment, a displacement (DISP) field which is the byte offset for locating any byte within the page. The page and displacement fields together provide a byte offset in the segment to any addressed byte. Whenever any byte in any segment is to be accessed with this segment address, a dynamic address translation mechanism (DATM) in the central processing unit performs the task of assigning a page frame to receive the page of the segment containing that byte. This assignment process assigns any available page frame in main store to the segment identifier and page fields in the segment address to form the assigned page frame field in the main store address shown in FIG. 6B. Thereafter the assigned page frame is substituted by DATM for the segment identifier and page field to provide the main store address of the byte, as shown in FIG. 6B. DATM puts the same displacement field in the main store address that it is given in the segment address.
When the addressing shown in FIGS. 6A and 6B is used, only a single segment may be assigned by the system to a page frame in the main store, which can result in most of the space in the page frame being wasted if the segment is small. For example, a segment which is a few hundred bytes in size may be the only segment in a page frame that is 4,096 bytes in size, resulting in over 3,000 bytes of hardware being unused in main store; this is highly inefficient. Of course, the user can put his data into parts of segments rather than in separate segments, but this throws a segment management burden on the user which he is often not equipped to handle. Putting several small data objects into parts of a single segment which occupies one or more page frames, would eliminate small segments, but then the user would have to provide his own "look-aside" directory for these packed data objects to locate them in each segment and provide all of the storage allocation overhead and management that this directory scheme would entail. The result burdens the user by making the system more difficult to use. To simplfy his use of the system, the user would ordinarily not attempt to combine unrelated small data objects into the same segment, and he would simply put each of them in a different segment, in order to be able to use automatic storage allocation features and automatic segment protection features provided in the system.
Making the page size smaller to approximate the size of the smallest segments, however, is also an undesirable design approach, since small page frame sizes may seriously impact the system hardware performance. This is because the system overhead for page handling increases rapidly as the page frame size is decreased. In general the overhead increases by a power of two each time the number of page frames is doubled. This dilemma may be referred to as the "small segment" problem.